package org.example.graph_theory;

import java.util.*;

public class timetable {
    public static void main(String[] args) {
        //课程表

        //你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
        //在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
        //例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
        //请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
        int numCourses = 2;
        int[][] prerequisites = {{0,1}};
        boolean b = canFinish(numCourses, prerequisites);
        System.out.println(b);
    }

    //39ms
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] len = new int[numCourses];

        for (int i = 0; i < prerequisites.length; i++) {
            int from = prerequisites[i][1], to = prerequisites[i][0];
            len[to]++;
        }

        boolean flag = true;
        HashSet<Integer> visited = new HashSet<>();

        while (flag){
            for (int i = 0; i < numCourses; i++) {
                if (visited.contains(i)) continue;
                if (len[i] == 0){
                    flag = false;
                    visited.add(i);
                    for (int j = 0; j < prerequisites.length; j++) {
                        int from = prerequisites[j][1], to = prerequisites[j][0];
                        if (from == i) len[to]--;
                    }
                }
            }
            flag = !flag;
        }

        return visited.size() == numCourses;
    }
}
